package LeetCode刷题.暑假刷的算法;

import java.util.Scanner;

/**
 * @program: Java_Study
 * @author: Xiaofan
 * @createTime: 2021-05-30 19:10
 * @description: Functions of this class is 删除链表（表中元素>0）重复项
 **/

public class 删除链表重复项 {
    public static void main(String args[]) {
        Node L = new Node();
        Scanner scanner=new Scanner(System.in);
        while (scanner.hasNext()) {
            int n = scanner.nextInt();
            L = insert_H(L, n);
            System.out.println("删除前的链表：");
            print(L);
            L = deleteSame2(L, n);
            System.out.println("删除后的链表：");
            print(L);
        }
    }

    private static class Node {
        Node next;
        String val;
    }
    private static Node deleteSame2(Node L,int n){//通过两层循环来去找到相同的节点并且删除
        Node head=L;
        if(head!=null&&head.next!=null){
            Node i=head.next;
            Node j=i;
            Node h=i;
            for(i=head.next;i.next!=null;i=i.next){
                String temp=i.val;
//                System.out.print(i.val);
                for(j=i.next;j.next!=null;j=j.next){
                    if(j.val.equals(temp)){
                        j.val=j.next.val;
                        j.next=j.next.next;
                    }
//                    System.out.print("-"+j.next.val);
                }
//                System.out.println();
            }
            return h;
        }
        return head;
    }
    private static Node deleteSame1(Node L,int n) {//通过数组标记删除相同的节点
        Node head = L;
        if (head != null && head.next != null) {//说明不是空节点或者单个节点
            boolean vis[] = new boolean[n+1];
            Node h=head;
            h=h.next;
            vis[Integer.parseInt(h.val)]=true;
            while (h.next!=null){
                if(vis[Integer.parseInt(h.next.val)]){
                    //如果下一个节点已经存在了
                    h.next=h.next.next;
                   continue;
                }
                vis[Integer.parseInt(h.next.val)]=true;
                h=h.next;
            }
        }
        return head;
    }

    private static Node insert_H(Node L,int n) {
        Node head = L;
        if (head != null) {
            Node r = head;
            Node l;
//            System.out.println(n);
            Scanner scanner=new Scanner(System.in);
            while (n-- > 0) {
                l = new Node();
                l.val = scanner.next();
                r.next = l;
                r = l;
            }
        }
        return head;
    }

    private static void print(Node L) {
        if (L != null) {
            Node head = L.next;
            while (head != null) {
                System.out.print(head.val + " ");
                head = head.next;
            }
            System.out.println();
        }
    }
}
